This invention relates to a method and apparatus for encoding/decoding image data. It is particularly applicable to the encoding/decoding of images that can be separated into their constituent parts as may be used in composite picture systems used in law enforcement, artistic creations, recreation and education.
It is known in the art to create images on the basis of components that are assembled to form a complete image. For example, a common technique for synthesizing single images of faces involves horizontally dividing the image of a face into bands for different features of the face such as hair, eyes, nose, mouth, and chin, respectively. Paper strips containing exemplary features are then be combined to form a composite drawing of a face. Yet another example involves a program element running on a computing platform which allows a user to select individual components and combining them on a pre-selecled face. In a typical interaction, the user first selects the shape of the face then eyes, nose, mouth and other components and combines them to form a facial image. Many variations on this theme can be used as described in Kakiyama et al. U.S. Pat. No. 5,600,767, Yoshino et al. U.S. Pat. No. 5,644,690, Sato et al. U.S. Pat. No. 5,537,662 and Belfer et al. U.S. Pat. No. 5,649,06 whose contents are hereby incorporated by reference. For example, the Sato et al. Patent, entitled Electronic Montage composing apparatus, describes a system for creating a montage image of a face using a plurality of basic parts stored in a library.
In constructing an image, pictorial entities are selected from a library of pictorial entities as assembled into images. These images may then be stored on a computer readable medium commonly referred to as a database or repository. Often, the storage of an image requires significant amounts of memory, often necessitating large repositories. For example, a composite picture system used in a police department often requires maintaining records of thousands of Individuals. The images are typically stored in files in some graphical format such as a xe2x80x9cbitmapxe2x80x9d, xe2x80x9cgifxe2x80x9d or xe2x80x9cjpegxe2x80x9d are other format. Although such encoding schemes provide a compressed representation of the image, the memory required for storing the image remains significant. In addition, compression methods of the type described above generally degrade the quality of the image. The size and quality of images is also particularly significant when the images are transmitted from one site to another via a digital link. For example, a given police station may transmit a composite picture to another police station in order to share information about a given suspect.
Thus, there exists a need in the Industry to refine the process of encoding images such as to reduce the memory requirements for storage and the bandwidth required for the transmission of the image.
The invention provides a novel method and an apparatus for encoding images.
For the purpose of the specification, the expression xe2x80x9cbasic elementsxe2x80x9d is used to describe a part of a specific image. In the preferred embodiment, a basic element is comprised of a pictorial entity conditioned by a set of image qualifiers. Examples of pictorial entities in a facial image are noses, eyes, mouths and eyebrows. In the preferred embodiment, pictorial entities are grouped into classes. For example, in composite picture system, all nose pictorial entities are grouped into the xe2x80x9cNOSExe2x80x9d class and all the eye pictorial entities are grouped in the xe2x80x9cEYExe2x80x9d class. Each class of pictorial entities is associated to a set of image qualifiers that are used to condition the pictorial entities in the associated class. The image qualifiers may include position qualifiers, zoom qualifiers, color qualifier and the likes.
For the purpose of this specification, the basic elements used in the special case of a facial image are referred to as xe2x80x9cbasic morphological elementsxe2x80x9d.
For the purpose of this specification, the word xe2x80x9csymbolxe2x80x9d is used to designate a representation of an object, image, qualifier or the likes. In a specific example, a symbol may be an index mapped to a memory location storing data elements such as a pictorial entity or image qualifier.
According to a broad aspect, the invention provides, a computer readable storage medium comprising a program element suitable for use on a computer having a memory. The program element is operative to create a first input to receive a set of element codes. The element codes characterized a portion of an image and included at least one symbol. A given symbol is a representation of a certain characteristic of the portion of the element code. A given symbol can acquire a set of possible values indicative of variations of the certain characteristic with which it is associated. The program element is also operative to create a second input to receive code factors associated to respective symbols of the set of element codes. A given code factor is assigned a value that exceeds the highest value that the symbol with which it is associated can acquire. The program element is operative to process the set of element codes to derive an image code. The image code is a compressed digital representation of the image, and is derived at least in part on the basis of the plurality of code factors. The image code can then be released as the output.
In a preferred embodiment, the image code is a number in a given base. Preferably, a large base is used in order to obtain a reduced number of characters in the image code.
In a preferred embodiment of the invention, the encoding method and apparatus is integrated into a picture system. The picture system creates images on the basis of images of basic individual parts, herein referred to as basic elements. In the preferred embodiment, the picture system includes a library of pictorial entities and qualifiers, an image builder unit, an encoding unit, a decoding unit and a factor table.
Each basic element in an image is assigned a unique identifier, herein referred to as element code. The element code contains information data elements, herein referred to as symbols. In a specific embodiment, the element code for each basic element includes a symbol that characterizes the pictorial element. In a preferred embodiment, the element code includes a plurality if symbols. In a specific example two (2) symbols are used namely an pictorial entity symbol and a position qualifier symbol. The element code may contain additional symbols without detracting from the spirit of the invention. For example symbols representative of other image qualifiers may be used such as color, zoom and other image effects may be used. An image is constructed by a set of basic elements. The basic elements present in a given facial image are said be xe2x80x9cactivexe2x80x9d in the given image. The set of active elements is stored in a data structure suitable for that purpose. In a specific example this data structure s an image data table. The image data table stores for each class a record, each record containing a set of fields, each field describing the active pictorial entity and qualifiers.
The number variations in each of the symbols for each of the classes is stored in a table, herein referred to as a code factor table. The code factor table provides information about the number of possible variations in an image. For each class, the code factor table stores a record, each record containing a set of fields, each field describing a maximum factor. The maximum factor in the code factor table is the largest identifier used for the given factor. Each symbol in the image data table is mapped to a factor in the code factor table.
According to another broad aspect, the invention provides an apparatus for encoding an image, the image comprising a set of basic elements, each basic element of the set of basic elements being associated to an element code. An encoding unit receiving as input the code factors and the element codes. The encoding unit processes the set of element codes to derive an image code, the image code being a compressed digital representation of the image derived at least in part on the basis of said plurality of code factors. The encoding unit then outputs the image code.
According to another broad aspect, the invention provides a method for encoding an image, the image comprising a set of basic elements, each basic element of the set of basic elements being associated to an element code. A processing step receives as input the code factors and the element codes to derive an image code. The image code is a compressed digital representation of the image derived at least in part on the basis of said plurality of code factors. The image code is the released.
In a preferred embodiment, the image code can be used to reproduce the image described by the image code. Image data may be obtained by combining the code factors and the image code with a decoding device. The image data is obtained by applying the inverse operations in the reverse order than those applied in the encoding process to the image code.
The image code allows each image to be described with a very small number of characters permitting the rapid transmission of the image over a data transmission medium. The receiving device has a decoding unit that is capable of extracting data information from the image code.
According to another broad aspect, the invention provides a method, apparatus and computer readable medium for decoding an image, the image comprising a set of basic elements, each basic element of the set of basic elements being associated to an element code. A processing step receives as input the code factors and the image code to derive the element codes. The element codes are then released.